{-# LANGUAGE TupleSections #-}

-- |
-- Module: Data.Vector.Sized.Shuffle
-- Copyright: (c) 2018 Koz Ross
-- Maintainer: Koz Ross <koz.ross@retro-freedom.nz>
-- Stability: Experimental
-- Portability: Non-portable
--
-- Implementation of Fisher-Yates shuffling for fixed-length arrays. This
-- produces a copy of the original; see "Data.Vector.Sized.Mutable.Shuffle" 
-- for an in-place version.
module Data.Vector.Sized.Shuffle where

import Control.Monad.Random.Strict
import Control.Monad.ST
import Data.Foldable
import GHC.TypeNats

import qualified Data.Vector.Generic as VG
import qualified Data.Vector.Generic.Mutable.Sized as VGMS
import qualified Data.Vector.Generic.Sized as VGS

-- |
-- Returns a shuffled copy of the input fixed-length vector.
--
-- __Complexity:__ \(O(n)\)
fisherYates ::
     (MonadRandom m, KnownNat n, VG.Vector v a)
  => VGS.Vector v n a
  -> m (VGS.Vector v n a)
fisherYates vec = do
  ixes <- traverse (getRandomR . (0, )) [0 .. VGS.length vec - 2]
  let v' =
        runST
          (do v <- VGMS.unsafeNew
              VGS.copy v vec
              traverse_ (uncurry (VGMS.unsafeSwap v)) (zip [0 ..] ixes)
              VGS.unsafeFreeze v)
  return v'
